Sàng Eratosthene

Sàng Eratosthenes là một giải thuật cổ xưa để lập bảng tất cả các số nguyên tố nhỏ hơn một số n {\displaystyle n} cho trước. Giải thuật dựa trên tính chất: mọi hợp số n {\displaystyle n} đều có ước nguyên tố không vượt quá căn của chính nó ( n {\displaystyle {\sqrt {n}}} ).Giải thuật đầu tiên xóa số 1 ra khỏi tập các số nguyên tố.Số tiếp theo số 1 là số 2, là số nguyên tố.Bắt đầu từ số 2 xoá tất cả các bội của 2 ra khỏi bảng.Số đầu tiên không bị xoá sau số 2 (số 3) là số nguyên tố.Tiếp theo lại xoá các bội của 3...Giải thuật tiếp tục cho đến khi găp số nguyên tố lớn hơn hoặc bằng sqrt(n) thì dừng lại. Tất cả các số chưa bị xoá là số nguyên tố.Theo ngôn ngữ thuật toán ta có thể diễn đạt giải thuật sàng Eratosthene như sau:

Eratosthene(n) Var List Prime[1..n] Int i,j,k for i:=1 to n Prime[i]:=TruePrime[1]:=falsek=0while k < sqrt(n) {i=k+1while Prime[i]=False i:=i+1k=ij=2while k*j<=n { Prime[k*j]:= Falsej:=j+1}}